import java.util.HashMap;

public class Solution {
    public static void main(String[] args) {
       int[] nums =  {1,1,1};
       subarraySum(nums,2);
    }
    //除自身以外的乘积
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int[] answer = new int[n];
        int[] f = new int[n];
        //f[i]表示i位置之前的前缀积
        f[0] = 1;
        for(int i = 1; i < n; i++) {
            f[i] = f[i-1] * nums[i-1];
        }
        int[] g = new int[n];
        g[n - 1] = 1;
        //g[i]表示i+1位置到n-1位置的后缀积
        for(int i = n - 2; i >= 0; i--) {
            g[i] = g[i+1] * nums[i+1];
        }
        for(int i = 0; i < n; i++) {
            answer[i] = f[i] * g[i];
        }
        return answer;
    }

    //和为 K 的子数组
    public static int subarraySum(int[] nums, int k) {
        int n = nums.length;
        //前缀和加哈希表
        HashMap<Integer,Integer> hash = new HashMap<>();
        hash.put(0,1);
        //前缀和为sum-k的个数
        int sum = 0; int ret = 0;
        for(int i = 0; i < n; i++) {
            sum += nums[i];
            if(hash.containsKey(sum - k)) {
                ret += hash.get(sum - k);
            }
            if(hash.containsKey(sum)) {
                hash.put(sum,hash.get(sum)+1);
            }else{
                hash.put(sum,1);
            }
        }
        return ret;
    }
}
